<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8" >

<title>每日一题20201109（15. 三数之和） | 小克的blog</title>

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.7.2/css/all.css" integrity="sha384-fnmOCqbTlWIlj8LyTjo7mOUStjsKC4pOpQbqyi7RrhN7udi9RwhKkMHpvLbHG9Sr" crossorigin="anonymous">
<link rel="shortcut icon" href="https://woodywrx.gitee.io/blog/favicon.ico?v=1615823433634">
<link rel="stylesheet" href="https://woodywrx.gitee.io/blog/styles/main.css">



<link rel="stylesheet" href="https://unpkg.com/aos@next/dist/aos.css" />
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>



    <meta name="description" content="题目链接:  15. 三数之和

解法


暴力法
首先可以确定的是暴力法的时间复杂度是O(N³), 所以基本上不考虑此等解法。


排序+双指针
思路是先将数组排序（从小到大），然后固定数组的第一位。
定义2个指针（左右指针）分别指向定位..."/>
    <meta name="keywords" content="leetcode"/>
</head>
<body>

<div id="app" class="main">

    <div class="sidebar" :class="{ 'full-height': menuVisible }">
  <div class="top-container" data-aos="fade-right">
    <div class="top-header-container">
      <a class="site-title-container" href="https://woodywrx.gitee.io/blog">
        <img src="https://woodywrx.gitee.io/blog/images/avatar.png?v=1615823433634" class="site-logo">
        <h1 class="site-title">小克的blog</h1>
      </a>
      <div class="menu-btn" @click="menuVisible = !menuVisible">
        <div class="line"></div>
      </div>
    </div>
    <div>
      
        
          <a href="https://woodywrx.gitee.io/blog" class="site-nav">
            首页
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/tags" class="site-nav">
            标签
          </a>
        
      
        
          <a href="https://woodywrx.gitee.io/blog/post/about" class="site-nav">
            关于
          </a>
        
      
    </div>
  </div>
  <div class="bottom-container" data-aos="flip-up" data-aos-offset="0">
    <div class="social-container">
      
        
      
        
      
        
      
        
      
        
      
    </div>
    <div class="site-description">
      欢迎来到我的小窝~这里不仅有博客，也有日记。
    </div>
    <div class="site-footer">
      wuranxu's blog | <a class="rss" href="https://woodywrx.gitee.io/blog/atom.xml" target="_blank">RSS</a>
    </div>
  </div>
</div>


    <div class="main-container">
        <div class="content-container" data-aos="fade-up">
            <div class="post-detail">
                <h2 class="post-title">每日一题20201109（15. 三数之和）</h2>
                <div class="post-date">2020-11-09 20:08:27</div>
                
                <div class="post-content" v-pre>
                    <p>题目链接:  <a href="https://leetcode-cn.com/problems/3sum/">15. 三数之和</a></p>
<figure data-type="image" tabindex="1"><img src="https://upload-images.jianshu.io/upload_images/6053915-69e10b376ebe0244.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="image.png" loading="lazy"></figure>
<h4 id="解法">解法</h4>
<ul>
<li>
<p><s>暴力法</s></p>
<p>首先可以确定的是暴力法的时间复杂度是O(N³), 所以基本上不考虑此等解法。</p>
</li>
<li>
<p>排序+双指针</p>
<p>思路是先将数组排序（从小到大），然后固定数组的第一位。</p>
<p>定义2个指针（左右指针）分别指向定位数组的后一位和数组最后一位。</p>
<p>如果3个数字加起来比0小，则左指针右移，循环继续。</p>
<p>如果3个数字加起来比0大，则右指针左移，循环继续。</p>
<p>如果3个数字等于0，说明找到了结果，将3个数字放入结果数组中并把左指针右移，右指针左移。</p>
<ol>
<li>
<p>这里需要注意的是，可能会有重复数据产生，为了不产生重复数据，需要确保左移/右移后的值与之前不一致。</p>
</li>
<li>
<p>如果从固定的数字大于0了，说明右侧不可能有结果了，因为右侧都是大于0的数字，加起来不会大于0了。</p>
</li>
<li>
<p>如果固定位置与上一个固定位置的值相同，也会产生重复数据，遇到直接跳过就行。</p>
</li>
</ol>
</li>
</ul>
<figure data-type="image" tabindex="2"><img src="https://upload-images.jianshu.io/upload_images/6053915-1956974a795b240a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240" alt="image.png" loading="lazy"></figure>
<h4 id="最终代码">最终代码</h4>
<pre><code class="language-Python">class Solution:
    def threeSum(self, nums: List[int]) -&gt; List[List[int]]:
        # 先对数组进行排序, 为了方便比较元素
        nums = sorted(nums)
        i = 0  # 数组起点
        result = []    # 结果
        while i &lt; len(nums):
            if nums[i] &gt; 0:
                # 大于0的数字可以直接跳过
                break
            if i &gt; 0 and nums[i] == nums[i-1]:
                # 与上一个固定位重复的数字直接跳过
                i += 1
                continue 
            front, back = i+1, len(nums)-1
            while front &lt; back:
                val = nums[i] + nums[back] + nums[front]
                if val &lt; 0:
                    # 说明需要增大数字, front+1
                    front += 1
                elif val &gt; 0:
                    # 说明需要缩小数字, back-1
                    back -= 1
                else:
                    result.append([nums[i], nums[back], nums[front]])
                    front += 1
                    back -= 1
                    # 保证没有重复数组
                    while front &lt; len(nums) and nums[front] == nums[front-1]:
                        front += 1
                    while back &gt;= 0 and nums[back] == nums[back+1]:
                        back -= 1
            i += 1
        return result
</code></pre>

                </div>
                
                    <div class="tag-container">
                        
                            <a href="https://woodywrx.gitee.io/blog/vp-bY7-nD/" class="tag">
                                leetcode
                            </a>
                        
                    </div>
                

                
                    <div class="next-post">
                        <div class="next">下一篇</div>
                        <a href="https://woodywrx.gitee.io/blog/post/mei-ri-yi-ti-20201106169-duo-shu-yuan-su/">
                            <h3 class="post-title">
                                每日一题20201106（169. 多数元素）
                            </h3>
                        </a>
                    </div>
                
                
                    <span id="/blog/post/mei-ri-yi-ti-2020110915-san-shu-zhi-he/"
                          class="leancloud_visitors" data-flag-title="每日一题20201109（15. 三数之和）">
                <em class="post-meta-item-text">阅读量 </em>
                <i class="leancloud-visitors-count">0</i>
            </span>
                
                
                    

	<div id="vcomments" style="width: 100%;max-width:1000%;padding:2.5%"></div>



                

            </div>

        </div>
    </div>
</div>

<script src="https://unpkg.com/aos@next/dist/aos.js"></script>
<script type="application/javascript">

AOS.init();

var app = new Vue({
  el: '#app',
  data: {
    menuVisible: false,
  },
})

</script>






<script src='https://cdn.jsdelivr.net/npm/valine/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        appId: 'fT8wvEVNtx1cOcCQEs7rVwnV-gzGzoHsz',
        appKey: 'xV6aDHKSkLfP7u0cBRIzpmcy',
        avatar: '',
        pageSize: 5,
        recordIp: true,
        placeholder: 'Just Go Go',
        visitor: true,
    });
</script>
<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
</body>
</html>
